package 链表;

import Utils.ListNode;

import java.util.PriorityQueue;

/**
 * @author: TTDB
 * @create: 2025/9/17
 */
public class mergeKLists {
    // 合并k个链表------Two的升级，试试看合并---方法可行
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        ListNode head = lists[0];
        for(int i = 0; i < lists.length; i++){
            head = mergeTwoLists(head, lists[i]);
        }
        return head;
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 == null ? l2 : l1;
        return dummy.next;
    }

    //除了两个两个的和，还可以使用最小堆
    public ListNode mergeKLists2(ListNode[] lists) {
        //创建一个最小堆
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);//降序
        for (ListNode node : lists) {
            if (node != null) {
                pq.offer(node);//把所有非空链表的头节点入堆
            }
        }
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (!pq.isEmpty()) {
            ListNode node = pq.poll();
            if (node.next != null) { //下一个节点不为空
                pq.offer(node.next); //下一个节点有可能是最小节点，入堆
            }
            cur.next = node; //把node添加到新链表的末尾
            cur = cur.next; //准备合并下一个节点
        }
        return dummy.next;//哨兵节点的下一个节点就是新链表的头节点

    }
}
